#include<stdio.h>
//typedef struct ListNode ListNode;
//class Solution {
//public:
//    ListNode* removeElements(ListNode* head, int val) {
//        ListNode* newhead, * newtail;
//        newhead = newtail = NULL;
//        ListNode* pcur = head;
//        while (pcur)
//        {
//            if (pcur->val != val)
//            {
//                if (newhead == NULL)
//                {
//                    newhead = newtail = pcur;
//                }
//                else
//                {
//                    newtail->next = pcur;
//                    newtail = pcur;
//                }
//            }
//            pcur = pcur->next;
//        }
//        if (newtail)
//            newtail->next = NULL;
//        return newhead;
//    }
//
//};

//typedef struct ListNode ListNode;
//class Solution {
//public:
//    ListNode* reverseList(ListNode* head) {
//        if (head == NULL)
//            return head;
//        ListNode* pcur1, * pcur2, * pcur3;
//        pcur1 = NULL, pcur2 = head, pcur3 = head->next;
//        while (pcur2)
//        {
//            pcur2->next = pcur1;
//            pcur1 = pcur2, pcur2 = pcur3;
//            if (pcur3)
//                pcur3 = pcur3->next;
//        }
//        return pcur1;
//    }
//};

//typedef struct ListNode ListNode;
//class Solution {
//public:
//    ListNode* middleNode(ListNode* head) {
//        ListNode* slow = head, * quick = head;
//        while (quick && quick->next)
//        {
//            slow = slow->next;
//            quick = quick->next->next;
//        }
//        return slow;
//    }
//};

//typedef struct ListNode ListNode;
//class Solution {
//public:
//    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
//    {
//
//        ListNode* pcur1 = list1, * pcur2 = list2;
//        if (pcur1 == NULL)
//        {
//            return pcur2;
//        }
//        if (pcur2 == NULL)
//        {
//            return pcur1;
//        }
//        ListNode* newhead, * newtail;
//        newhead = newtail = (ListNode*)malloc(sizeof(ListNode));
//        while (pcur1 && pcur2)
//        {
//            if (pcur1->val > pcur2->val)
//            {
//                newtail->next = pcur2;
//                newtail = pcur2;
//                pcur2 = pcur2->next;
//            }
//            else
//            {
//                newtail->next = pcur1;
//                newtail = pcur1;
//                pcur1 = pcur1->next;
//            }
//        }
//        if (pcur1)
//        {
//            newtail->next = pcur1;
//        }
//        else if (pcur2)
//        {
//            newtail->next = pcur2;
//        }
//        ListNode* ret = newhead->next;
//        free(newhead);
//        newhead = newtail = NULL;
//        return ret;
//    }
//};

